package cn.bouncyslime.algorithms.dynamicPlan.rabbitGetRidish;

/*
*   小白兔拔萝卜问题
*
*   在结果数组中，如果右边和下边相等的话，默认选择下边
*
* */

public class Main {

    public void resolve(int[][] ridishArray, int[][] resultArray){
        // 计算结果数组中的最后一行
        int flag = ridishArray.length-1;
        for(int i=ridishArray[flag].length-1; i>=0; i--){
            if(i==ridishArray[flag].length-1){
                resultArray[flag][i] = ridishArray[flag][i];
            }else{
                resultArray[flag][i] = ridishArray[flag][i] + resultArray[flag][i+1];
            }
        }
        // 计算结果数组中的最后一列
        int flag2 = ridishArray[0].length-1;
        for(int i=ridishArray.length-2; i>=0; i--){
            resultArray[i][flag2] = ridishArray[i][flag2] + resultArray[i+1][flag2];
        }
        // 计算结果数组中的其他部分
        for(int i=ridishArray.length-2; i>=0; i--){
            for(int j=ridishArray[i].length-2; j>=0; j--){
                int flag3 = ridishArray[i][j] + resultArray[i+1][j];    // 和下面相加
                int flag4 = ridishArray[i][j] + resultArray[i][j+1];    // 和右面相加
                if(flag3>=flag4){
                    resultArray[i][j] = flag3;
                }else{
                    resultArray[i][j] = flag4;
                }
            }
        }
    }

    // 用来寻找最优路径，用最后结果减去萝卜田此处的萝卜数量，之后判断是从下边来还是从右边来
    public void getBestRoad(int[][] bestRoad, int[][] ridishArray, int[][] resultArray){
        int result = resultArray[0][0];
        int x=0, y=0;
        bestRoad[x][y] = 1;
        while(true){
            result -= ridishArray[x][y];
            // 当到达最后行时，此时只能从右边来
            if(x==ridishArray.length-1){
                for(int i=y+1; i<ridishArray[x].length; i++){
                    bestRoad[x][i] = 1;
                }
                break;
            }
            // 当到达最后列时，此时只能从下边来
            if(y==ridishArray[x].length-1){
                for(int i=x+1; i<ridishArray.length; i++){
                    bestRoad[i][y] = 1;
                }
                break;
            }
            // 判断从下来还是从右来
            if(resultArray[x+1][y] == result){
                bestRoad[x+1][y] = 1;
                x++;
            }else if (resultArray[x][y+1] == result){
                bestRoad[x][y+1] = 1;
                y++;
            }
            // 当到达出口时，程序退出
            if(x==ridishArray.length-1 && y==ridishArray[x].length-1){
                break;
            }
        }
    }

    // 用来打印输出二维数组
    public void printArray(int[][] array){
        for(int i=0; i<array.length; i++){
            for(int j=0; j<array[i].length; j++){
                System.out.printf("%4d" , array[i][j]);
            }
            System.out.println();
        }
    }
    // 用来初始化二维数组
    public void initArray(int[][] array, int num){
        for(int i=0; i<array.length; i++){
            for(int j=0; j<array[i].length; j++){
                array[i][j] = num;
            }
        }
    }

    public static void main(String[] args){
        int[][] ridishArray = {{2,3,1,2,4}, {3,2,4,3,3}, {2,3,3,3,2}, {2,0,2,4,1}, {3,20,2,2,2}};
        int[][] resultArray = new int[ridishArray.length][ridishArray[0].length];
        int[][] bestArray = new int[ridishArray.length][ridishArray[0].length];

        Main m = new Main();
        System.out.println("萝卜田为：");
        m.printArray(ridishArray);
        m.initArray(resultArray, 0);
        m.resolve(ridishArray, resultArray);
        m.initArray(bestArray, 0);
        m.getBestRoad(bestArray, ridishArray, resultArray);
        System.out.println("拾萝卜数组为：");
        m.printArray(resultArray);
        System.out.println("最优路径数组为：");
        m.printArray(bestArray);
    }
}
